The invention relates to the field of data communication networks. More particularly, the present invention relates to methods and apparatus for scheduling data packets being sent within a data communication network.
In a network that serves multiple user entities for various different purposes, it is important that the resources of the network are allocated appropriately. For example, it may be desired to dynamically allocate network resources between important or time-critical communications and those that are of lower importance or are less time-critical. This is to ensure that all communications reach their destinations when needed (or least to ensure that only low importance communications are subject to significant delays). For example, certain communications may be intolerant to delays, such as voice or video communications. In addition, certain network users may desire higher levels of network availability than others. Conversely, other users or other types of communications, such as batch file transfers, may be more tolerant of communication delays.
In network equipment, such as switches or routers, data packets are typically received and buffered prior to retransmission. The equipment then forwards the data packets to their appropriate destinations and may also perform other functions. For example, each piece of network equipment may allocate network resources to the various data communications it receives by appropriately scheduling its buffered packets before forwarding them. As computer networks evolve, there is an ever-increasing need to provide more bandwidth, lower latency, decreased costs and increased flexibility. Accordingly, there is a need to provide techniques for scheduling the retransmission of data packets that respond to these needs.
A conventional technique for scheduling retransmission of data packets involves the use of a heap data structure. Packets awaiting retransmission are placed in the heap and arranged in accordance with their priorities prior to retransmission. Further, network switches or routers typically provide multiple ports and/or transmission channels that may be used for re-transmitting packets received by the switch or router. Accordingly, what is needed is a technique for efficiently and flexibly scheduling retransmission of packets via several ports and communication channels. What is also needed is a technique for arranging the heap quickly and efficiently.
Aspects of the invention are variously directed to these ends.
The present invention is directed toward methods and apparatus for data packet transmission scheduling using a partitioned scheduling heap data structure. The scheduling heap data structure has a plurality of levels for storing scheduling values for data packets according to their relative priorities. A highest level in the heap has a single position and each succeeding lower level has twice the number of positions as the preceding level. The data structure may be adapted to store a plurality of logical heaps within the heap data structure by assigning a highest level of each logical heap to a level in the heap data structure that is lower than the highest level. Thus, a single physical memory may be adapted to store plural logical heaps. This is useful because a single physical memory can be adapted to prioritize packets of various different transmission protocols and speeds.